Searching for data that matches a query takes place in a large variety of circumstances. For example, a word-match search may be used to identify occurrences of a keyword in a document, a database of documents, or in online internet webpage searching. Login verification may involve searching for a match in a set of login credentials. Object recognition may involve searching through a database or collection of objects for a matching object. All these examples can be generalized as a two-step process: (1) construct the set S and its representation, typically offline, and (2) compute ƒ(x), where x is the query and ƒ(x) is the result according to:
      f    ⁡          (      x      )        =      {                            0                                      x            ∉            S                                                1                                      x            ∈            S                              
The second step—membership testing—is typically done “online”, often in real-time.
Many modern searches are not necessarily based on perfect matches. For example, object or feature recognition in images or video cannot typically rely on perfect matching. For example, some facial recognition processes may want to identify close matches, as opposed to perfect matches. Fingerprint analysis is another area in which exact matches are unlikely. Instead, in these “imperfect” match searches, a distance-based matching may be used. The term “distance-based” is used in the general sense of a scalar metric d(x, y) where x is a query and y is a candidate element of S. In some cases, the metric d(x, y) may be the Euclidean distance, but other more complex metrics may be used.
With distance-based matching, the search result, ƒ(x) is based on whether there is an element(s) of the set S within a threshold distance δ of the query x. The search for the closest element of S subject may be described as:
      d    ⁡          (              x        ,        S            )        =            min              y        ⁢                                  ∈                                  ⁢        S              ⁢          d      ⁡              (                  x          ,          y                )            
With the constraint of the threshold distance, the search may be characterized as:
      f    ⁡          (      x      )        =      {                            0                                                    d              ⁡                              (                                  x                  ,                  S                                )                                      >            δ                                                1                                                    d              ⁡                              (                                  x                  ,                  S                                )                                      ≤            δ                              
It will be appreciated that distance-based searching is significantly more costly (in terms of computing resources) and time-consuming than simple membership testing. As a result, imperfect match searching can be difficult to implement in real-time online searching, particularly where the metric d(x, y) is complex.
Similar reference numerals may have been used in different figures to denote similar components.